#pragma once
#include <string.h>
#define HASH_TABLE_SIZE 20017
#define HASH_BASE 31

struct KVpairs {
	void* val; // 指向值所在内存段的指针
	void* key; // 指向键所在内存段的指针
	int code; // +: 占用, 0: 空闲, -: 已解绑
}; // 键值对结构

typedef unsigned char byte;
typedef struct KVpairs kvp;
typedef kvp table[HASH_TABLE_SIZE]; // table只是一个普通的数组，不提供内存管理功能，键值对占用的内存需要自行准备

int hash(const void* bytes, size_t count); // 哈希函数
int tb_find(table, const char* key); // 查询键在表中的实际位置，返回位置或0

void* tb_get(table, const char* k); // 获取值的内存地址，不存在则返回NULL
int tb_set(table, const char* k, const void* v); // 设置值的内存地址，返回错误或0

int tb_pull(table, const char* k, char* v, size_t); // 从已经设置好的内存中拉取值的字符串副本
int tb_push(table, const char* k, const char* v); // 推送值的字符串副本到已经设置好的内存中

int kvp_unset(kvp*); // 将键值对设为解绑状态
int tb_del(table, const char* k); // 解绑一个键值对，以便这个空位可以容纳新的键值对
int tb_pop(table, const char* k, kvp*); // 解绑 的同时弹出一个副本

void tb_clear(table); // 强制置零整个table内存段
int tb_len(table); // 获取table长度
kvp* next(table, const kvp*); // 查找下一个键值对，没有了就返回NULL

// 适用于for遍历table
#define in_pairs(tb, kv) kv=next(tb,tb);kv;kv=next(tb,kv)



// ------- 具体实现 ------- //

// 适用于for遍历线性探测序列
#define in_acclist(tableHeader, currentPair, index) \
currentPair = tableHeader + index; \
index < HASH_TABLE_SIZE && currentPair->code; \
currentPair++, index++

// 适用于if判断是否匹配给定的键
#define kmatch(kvPair, givenKey) \
(kvPair->key && strcmp((char*)kvPair->key, givenKey) == 0)

// table长度是否已经初始化
#define len_inited(tableHeader) \
((tableHeader)->key && *(char*)(tableHeader)->key == 'n' && !*((char*)(tableHeader)->key + 1))

// 计算整数幂的函数
static inline unsigned long long ipow(unsigned long long base, unsigned exp) {
    long long result = 1;
    
    while (exp > 0) {
        if (exp & 1) result *= base;
        base *= base;
        exp >>= 1;
    }
    return result;
}


int hash(const void* bytes, size_t count) {
	int counter = 0;
	unsigned long long int sum = 0;
	
	for (byte *currentByte = (byte*)bytes; counter < count; currentByte++, counter++)
		sum += (unsigned int)(*currentByte) * ipow(HASH_BASE, count-counter-1);
	
	return 1 + sum%(HASH_TABLE_SIZE-1);
}


int tb_find(table tb, const char* key) {
	if (!key) return -1; // 错误：空指针

	int pos = hash(key, strlen(key));
	
	for (kvp* in_acclist(tb, pair, pos))
		if (kmatch(pair, key))
			return pos;
	
	return -1; // 错误：没有这个键
}


void* tb_get(table tb, const char* key) {
	if (!key) return NULL; // 错误：空指针
	
	int pos = hash(key, strlen(key));
	
	for (kvp* in_acclist(tb, pair, pos))
		if (kmatch(pair, key))
			return pair->val;
	
	return NULL; // 错误：没有这个键
}


int tb_set(table tb, const char* key, const void* val) {
	if (!key || !val) return 1; // 错误：空指针
	
	const int hashCode = hash(key, strlen(key));
	int pos = hashCode, isNew = 1;
	kvp *pair;
	
	for (in_acclist(tb, pair, pos)) {
		if (pair->code < 0) {
			break; // 允许复用已经解绑的槽
		} else if (kmatch(pair, key)) {
			isNew = 0; // 更新指向而不是新增
			break;
		}
	} // 跳过聚集区

	if (pos >= HASH_TABLE_SIZE)
		return 1; // 错误：没有多余空位

	pair->code = hashCode;
	pair->key = (void*)key;
	pair->val = (void*)val;
	
	if (isNew && len_inited(tb))
		tb->code++; // table长度+1
	return 0; // 成功设置
}


int tb_pull(table tb, const char* key, char* out, size_t size) {
	if (!out || !size) return 0;

	int idx = tb_find(tb, key);
	if (idx == -1 || strlen(tb[idx].val) >= size)
		return 0; // 错误：没有这个键或空间不足
	
	strcpy(out, tb[idx].val);
	return 1;
}


int tb_push(table tb, const char* key, const char* val) {
	if (!val) return 1;

	int idx = tb_find(tb, key);
	if (idx == -1) return 1;

	strcpy(tb[idx].val, val);
	return 0;
}


inline int kvp_unset(kvp* pair) {
	if (!pair) return 1;
	pair->key = NULL;
	pair->val = NULL;
	pair->code *= -1;
	return 0;
}


int tb_del(table tb, const char* key) {
	if (!key) return 1; // 错误：空指针
	
	int pos = hash(key, strlen(key));
	
	for (kvp* in_acclist(tb, pair, pos))
		if (kmatch(pair, key)) {
			pair->key = NULL;
			pair->val = NULL;
			pair->code *= -1;
			
			if (len_inited(tb))
				tb->code--; // table长度-1
			return 0;
		}
	
	return 1;
}


int tb_pop(table tb, const char* key, kvp* out) {
	if (!key || !out) return 1; // 错误：空指针
	
	int pos = hash(key,strlen(key));
	
	for (kvp* in_acclist(tb, pair, pos))
		if (kmatch(pair, key)) {
			*out = *pair; // 保存副本
			
			pair->key = NULL;
			pair->val = NULL;
			pair->code *= -1;
			
			if (len_inited(tb))
				tb->code--; // table长度-1
			return 0;
		}
	
	return 1;
}


inline void tb_clear(table tb) {
	memset(tb, 0, sizeof(table));
}


int tb_len(table tb) {
	if (len_inited(tb)) // 长度已经计算过
		return tb->code;
	
	int len = 0;
	kvp *p = tb, *end = tb + HASH_TABLE_SIZE;
	for (; p < end; p++)
		if (p->code > 0) len++;
	
	tb->key = tb->val = "n";
	tb->code = len;
	return len;
}


kvp *next(table tb, const kvp* pair) {
	kvp *end = tb + HASH_TABLE_SIZE;
	
	for (pair++; pair < end; pair++)
		if (pair->code > 0)
			return (kvp*)pair;
	
	return NULL;
}

#undef in_acclist
#undef kmatch
#undef len_inited

// 可选参数宏
#define __get5th(a, b, c, d, e, ...) e
#define __nparams(...) __get5th(__VA_ARGS__, 4, 3, 2, 1, 0)

#define __tb_pull_3(tb, key, val) tb_pull(tb, key, val, sizeof(val))
#define __tb_pull_4(tb, key, val, size) tb_pull(tb, key, val, size)
#define __tb_pull_cat(n, ...) __tb_pull_##n(__VA_ARGS__)
#define __tb_pull_expand(...) __tb_pull_cat(__VA_ARGS__)
#define tb_pull(...) __tb_pull_expand(__nparams(__VA_ARGS__), __VA_ARGS__)

#define __next_1(tb) next(tb, tb)
#define __next_2(tb, pair) next(tb, pair)
#define __next_cat(n, ...) __next_##n(__VA_ARGS__)
#define __next_expand(...) __next_cat(__VA_ARGS__)
#define next(...) __next_expand(__nparams(__VA_ARGS__), __VA_ARGS__)